Conventionally, when managing large volume data with a tree structure, a B-tree data structure is relatively often used. As a B-tree stores multiple data entries (hereinafter, referred to as entries) in one block, it has an advantage in that the range affected by the change of the form of the tree structure becomes small when an entry is added, compared to a simple binary tree. Thus, a B-tree is often used as a data management method for disks such as hard disks.
However, when searching data managed on the disk with a tree structure, it is necessary to read multiple data blocks. Moreover, as the speed of I/O (input/output) to the disk is generally slower than that of the memory access, it may take time and trouble to search data on the disk. Therefore, recently, there has been considered of a method of having a tree structure in a memory to prevent the delay of search caused by the disk I/O. However, in a B-tree, when the number of entries increases, the amount of necessary memory may increase in response to the increase of the number of entries. Thus, a method of using a method of storing the part which is most frequently read in the tree structure to the memory (cache) has been considered.
Recently, there has been known a data structure which is called a Bloom Filter. The Bloom Filter is a method of examining whether a certain entry belongs to an existing set efficiently, as disclosed in Japanese Patent Application Publication No. 2007-52698 for example.